package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode
import java.util.*

/**
 * @author flutterdash@qq.com
 * @since 2021/4/30 12:01
 */
class P230 {

    fun kthSmallest(root: TreeNode?, k: Int): Int {
        root!!

        val stack = Stack<TreeNode>()
        var node = root
        var res = root.`val`
        var count = 0

        while (stack.isNotEmpty() || node != null) {
            while (node != null) {
                stack.push(node)
                node = node.left
            }

            node = stack.pop()
            res = node.`val`
            count++
            if (count == k)
                return res
            node = node.right

        }

        return res
    }

    @Test
    fun test0() {
        val node1 = TreeNode(1)
        val node2 = TreeNode(2)
        val node3 = TreeNode(3)
        val node4 = TreeNode(4)
        val node5 = TreeNode(5)
        val node6 = TreeNode(6)

        node5.left = node3 // root
        node5.right = node6

        node3.left = node2
        node3.right = node4

        node2.left = node1

        Console.log(kthSmallest(node5, 3))
    }

}
